class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int n = prices.size();
        if (n == 1)
        {
            return 0;
        }
        vector<int> leftMin(n);
        leftMin[0] = prices[0];
        for (int i = 1; i < n; ++i)
        {
            leftMin[i] = min(leftMin[i - 1], prices[i]);
        }
        int rightMax = prices[n - 1];
        int profit = rightMax - leftMin[n - 1];
        for (int i = n - 2; i >= 0; --i)
        {
            rightMax = max(rightMax, prices[i]);
            int thisProfit = rightMax - leftMin[i];
            profit = max(thisProfit, profit);
        }
        return profit;
    }
};